"""
难度：简单
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
"""
from typing import List


class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        size = len(arr)
        if k <= 0 or not arr:
            return []
        if size <= k:
            return arr
        self.buildMaxHeap(arr,k)
        for i in range(k,size):
            if arr[i] < arr[0]:
                arr[i],arr[0] = arr[0],arr[i]
                self.heapify(arr,0,k-1)
        return arr[:k]

    def heapify(self,nums:List[int],index:int,end:int):
        left = index* 2 + 1
        right = left + 1
        while left <= end:
            max_index = index
            if nums[left] > nums[max_index]:
                max_index = left
            if right <= end and nums[right] > nums[max_index]:
                max_index = right
            if index == max_index:
                break
            nums[index], nums[max_index] = nums[max_index], nums[index]

            index = max_index
            left = index*2 +1
            right = left +1
    # 初始化大顶堆
    def buildMaxHeap(self,nums:List[int],k:int):
        for i in range((k-2)//2,-1,-1):
            self.heapify(nums,i,k-1)
        return nums
        